def get_max_val(values, weights, capacity):
    # 过滤不合理的值
    if values is None or len(values) == 0:
        return 0
    if weights is None or len(weights) == 0:
        return 0
    if capacity < 0:
        return 0

    # 使用递推方式:dp[i][j]:最大承重为j，有前i件物品可选时的最大总价值
    dp = [[0] * (capacity + 1) for _ in range(len(values) + 1)]

    # 遍历
    for i in range(1, len(values) + 1):
        for j in range(1, capacity + 1):
            # 翻译状态转移方程
            if j < weights[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])

        # 打印物品组合信息
        print_goods_info(dp, weights, values, capacity)
        print("---------------------")

    return dp[len(values)][capacity]


def print_goods_info(dp, weights, values, capacity):
    # 从后往前遍历二维数组
    i = len(weights)
    j = capacity
    while i > 0 and j > 0:
        try:
            if dp[i][j] == dp[i - 1][j - weights[i - 1]] + values[i - 1]:
                # 说明选择了这件物品
                print(f"选择了价值为{values[i - 1]}的物品")
                j = j - weights[i - 1]
        except IndexError:
            pass
        # 不管是否选择了物品，i都要移动到上一行
        i -= 1


if __name__ == "__main__":
    values = [6, 3, 5, 4, 6]
    weights = [2, 2, 6, 5, 4]
    capacity = 10
    result = get_max_val(values, weights, capacity)
    print(f"最大总价值为: {result}")